import copy
import sortedcontainers
class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        m = len(matrix)
        n = len(matrix[0])
        prefix = copy.deepcopy(matrix)
        max_val = -float('inf')
        for i in range(m):
            for j in range(1, n):
                prefix[i][j] += prefix[i][j - 1]
        for i in range(n):
            for j in range(i, n):
                if i == 0:
                    new_prefix = [prefix[t][j] for t in range(m)]
                else:
                    new_prefix = [prefix[t][j] - prefix[t][i - 1] for t in range(m)]
                for t in range(1, m):
                    new_prefix[t] += new_prefix[t - 1]
                p = sortedcontainers.SortedList([0])
                for t in range(m):
                    index = p.bisect_left((new_prefix[t] - k))
                    if index < t + 1:
                        val = new_prefix[t] - p[index]
                        if val == k:
                            return val
                        else:
                            max_val = max(val, max_val)
                    p.add(new_prefix[t])
        return max_val


data = Solution()
matrix = [[1, 0, 1], [0, -2, 3]]
k = 5
print(data.maxSumSubmatrix(matrix, k))
matrix = [[2, 2, -1]]
k = 3
print(data.maxSumSubmatrix(matrix, k))
